#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* createTreeNode(char* str, int* index) {
    if (str[*index] == '#' || str[*index] == '\0') {
        (*index)++;
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = str[(*index)++];
    root->left = createTreeNode(str, index);
    root->right = createTreeNode(str, index);
    return root;
}

void inOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->val);
    inOrder(root->right);
}

void freeTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    free(root->left);
    free(root->right);
    free(root);
}

int main() {
    char* in = "abc##de#g##f###";
    int n = strlen(in);
    int index = 0;
    TreeNode* root = createTreeNode(in, &index);
    inOrder(root);
    freeTree(root);
    printf("\n");
    return 0;
}